Interval List Intersections
Leetcode #986 | Medium | Интервалы | Два указателя
Идея
Один указатель на первый лист (i), другой на второй лист (j). Идем while-ом, смотрим максимум из стартов и минимум из концов, если maxStart <= minEnd - то есть пересечение, добавляем в res [maxStart, minEnd], иначе пересечения нет. В конце двигаем тот указатель, где конец раньше закончился.
Big-O
- Время
O(N+M) - Память
O(1)
Код
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> res = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int start = Math.max(A[i][0], B[j][0]);
int end = Math.min(A[i][1], B[j][1]);
if (start <= end) res.add(new int[]{start, end});
if (A[i][1] < B[j][1]) i++; else j++;
}
return res.toArray(new int[0][0]);
}
}